Most instructions executed by a computer perform some type of arithmetic or logic operation on one or more data operands and produce resulting data. Typically, the instruction specifies one or more registers where the data operands are stored and a register where the result of the operation is to be stored. Some of these instructions can also generate side-effects or exceptions as a result of their operations, which are usually not reflected in the stored result. The occurrence of such exceptions is typically indicated by storing a status word containing a plurality of bits or flags in a status register.
Exemplary of instructions that may generate exceptions are floating-point operation instructions. Typical exceptions that can result from a floating point operation instruction are divide by zero, inexact, invalid, overflow, and underflow. Overflow and underflow exceptions, for example, are produced when a floating point add, subtract, multiply, or divide instruction results in a number beyond the finite range of representable floating point numbers. Divide by zero, inexact, and invalid exceptions are produced when a floating point operation instruction such as division by a zero operand results in an undefined number.
Usually, when an exception is generated as a result of an instruction it is not possible to continue program execution without taking corrective action. For example, when a floating point divide instruction produces a divide by zero exception, the result of the instruction is an undefined number. Subsequently executed instructions that use the floating point divide instruction result would produce erroneous or nonsensical data.
A variety of mechanisms have therefore been used to respond to the occurrence of exceptions. The simplest but most drastic response is a hardware mechanism that simply ends or aborts program execution when an exception occurs. This type of hardware mechanism prevents the result of the excepting instruction from being used to generate erroneous data since program execution is discontinued. However, the data produced by the program up to the occurrence of the exception is typically lost. When program execution is aborted, it may also be difficult to identify which instruction and which exception caused program execution to abort.
In most cases, though, exceptions can be handled by taking some corrective action so that program execution can continue or be halted without losing data. Typical corrective actions include displaying an error message, allowing the user to enter different input data before repeating a computation, or gracefully halting program execution while retaining data and identifying why the program was halted.
In some cases, it is also possible to continue program execution after an excepting instruction while avoiding producing erroneous results with subsequent instructions by substituting a default result for the result of the excepting instruction. For example, in some computations involving a floating point division operation, a result is defined for division by a zero operand. As a specific example, the function, sin(x)/x, when calculated in a computer involves dividing the value of sin(x) by the value of x with a floating point divide instruction. When x is zero, the floating point divide instruction will generate a divide by zero exception and an undefined floating point number result. However, this function is known to equal one for x equal to zero. By substituting one for the undefined result of the floating point divide instruction, the program can continue and subsequent instructions which use the substituted result will produce accurate data. In mathematical terms, this type of exception is known as a removable singularity. The corrective action of substituting a default result can be used for other exceptions produced by floating point operation and non-floating point operation instructions.
Corrective actions are generally carried out in software routines known as exception handlers. The exception handlers consist of instructions which display an error message, gracefully exit the program, substitute a default result, or take other corrective action. In general, exception handlers are specific to a particular exception and to a particular instruction in a program.
There are two common mechanisms for invoking an exception handler to take corrective action in response to exceptions. The mechanisms can be termed "tests and branches" and "traps." Tests and branches are a pure software mechanism which involves inserting instructions prior to a potentially excepting instruction to both test the values of the instruction's operands and branch to an appropriate exception handler if the values of the operands would cause an exception. For example, test and branch instructions can be inserted prior to a floating point divide instruction to test the divisor operand and branch to an exception handler if the divisor operand is zero. The exception handler can then take appropriate corrective action such as substituting a default result if such result is defined, and resuming program execution after the floating point divide instruction. The approach of placing test and branch instructions is particularly useful in computers which provide no hardware mechanism for handling exceptions or which simply end program execution when an exception is generated.
A trap is a hardware mechanism that is similar in some ways to externally generated interrupts. In computers with a trap mechanism, a set of locations in memory is set aside or dedicated for the purpose of storing the starting addresses of exception handlers. These stored starting addresses are termed trap vectors. Generally, there is one trap vector for each type of exception that can be produced by the computer. When an exception occurs, the trap mechanism temporarily suspends program execution and forcibly transfers execution from the program to the exception handler at the corresponding trap vector for the exception. The computer then executes the exception handler to take corrective action. Information concerning program execution (the program context) such as the address where program execution was interrupted and the current contents of the computer's registers is typically stored in a stack memory when the trap is generated. Storing the program context permits resumption of program execution after execution of the exception handler is complete. This type of program interrupt which permits resumption of the program at a particular point is known as a precise interrupt.
Both test and branch and trap mechanisms have the disadvantage of adding to software complexity and slowing program execution. With test and branch mechanisms, the programmer must insert several instructions before each potentially excepting instruction to test for various data that could produce an exception and to branch to appropriate exception handlers. Inserting the test and branch instructions complicates the programming task and adds to the size of the program. If the possibly excepting instruction is in a loop or other repeated routine, the added test and branch instructions impose a speed penalty on each iteration of the loop which severely affects the speed of program execution.
With trap mechanisms, a speed penalty is imposed only when an exception is actually produced by the excepting instruction. However, the speed penalty can still be significant since precise interrupts cause a time delay. Programming the exception handler may also be more complex, especially when the corrective action is simply to substitute a default result. Since the excepting instruction's result is usually stored in a register and register contents are stored along with the program's context in the stack memory, substituting the default result may require storing the substitute result in the correct location of the stack memory. This may require a number of push and pop operations to properly manipulate the stack memory.
Both of these mechanisms also pose problems in pipelined and vectorized computers which achieve faster program execution by overlapping or concurrent instruction execution. In a pipelined computer, instructions are executed in an assembly line fashion. Each instruction is executed in a series of stages, and several instructions at various stages of execution are executed concurrently. Some pipelined computers, for example, use three main stages: read, execute, and write. Each stage may also have a number of sub-stages. In the read stage, the instruction and its operands are read by the computer from memory or registers. In the execute stage, an operation for the instruction is performed on the operands. In the write stage, the result of the operation is formatted and transferred to register or memory storage. As the execute stage of one instruction is performed, a previous instruction is generally in its write stage and a next instruction is in its read stage. Since more than one instruction can be executed concurrently in a pipelined computer, a program generally runs much faster than in a non-pipelined computer.
In a pipelined computer, not all instructions of a program can be executed concurrently. Usually this is because there is some data dependency between instructions. For example, a situation known as a read after write hazard is created when the result of a first instruction is used as an operand of a subsequent instruction. Since the result is not available to be read until after it is written, the subsequent instruction cannot be executed concurrently with the first instruction. The read stage of the subsequent instruction must follow the write stage of the first instruction. Data dependencies can be avoided by shifting the order of instructions if possible or inserting null instructions between data dependent instructions during compiling of a program. Hardware which checks for data dependencies and inserts null instructions between data dependent instructions at run time also can be used.
Test and branch mechanisms are disadvantageous in a pipelined computer because they inherently obstruct concurrent instruction execution. Each time concurrence is inhibited, program execution is slowed. Until a branch instruction is executed, it is not known which of two instructions--the next instruction in sequence or a remote instruction--is to be executed next. Concurrence of instruction execution is therefore not possible. This disadvantage can be partially offset by hardware which attempts to predict which of the two instructions will follow the conditional branch instruction and begins executing the predicted instruction concurrently. However, the prediction is not always accurate. When the prediction proves inaccurate, the hardware must undo execution of the inaccurately predicted instruction and begin executing the other instruction. Thus, a speed penalty is still imposed when a branch is not accurately predicted. Such added hardware functionality adds to the cost and complexity of the pipelined computer.
Trap mechanisms also have the disadvantage of interrupting concurrence and adding to the complexity and cost of the hardware in a pipelined computer. To successfully return to program execution after transferring execution to an exception handler, a trap mechanism must perform a "precise interrupt" in which the state of program execution up to the excepting instruction is retained to permit resumption of program execution at the point of interruption. Since multiple instructions execute concurrently in a pipelined computer, some of the instructions following the excepting instruction will be in varying stages of execution. Some may have already altered the data in the computer's registers or the status bits in the exception register. To halt program execution at the excepting instruction, the trap mechanism must be able to "drain" the pipeline of other concurrently executing instructions. Draining the pipeline may require recalling what other instructions subsequent to the excepting instruction have done and undoing their effects. Such hardware which can precisely interrupt pipelined instructions is more complex and expensive because it must be able to remember and undo multiple concurrent instructions.
Some pipelined computers simplify the trap mechanism by requiring that a barrier operation instruction be inserted after a potentially excepting instruction. The barrier operation instruction inhibits concurrence by preventing subsequent instructions from executing concurrently with the potentially excepting instruction. This, in effect, drains the instruction pipeline to permit trapping or branching to an exception handler. The drawback to barrier operation instruction mechanisms is that concurrence is inhibited every time an instruction that could generate an exception is executed.
The present invention provides a method and apparatus for recovery from exceptions that overcomes these and other drawbacks of the prior art. According to the invention, the instruction set of a computer (which can be a pipelined computer) is enhanced by including one or more "fix-up" instructions that effect a simple corrective action such as substituting a default value in response to an instruction producing one or more specified exceptions.
In one embodiment of the invention, for example, a conditional substitution instruction is included in a pipelined computer's instruction set. The conditional substitution instruction specifies a set of one or more possible exceptions, a default value, and a result register. The conditional substitution instruction is inserted in a program after a potentially excepting instruction for which substituting the default result will permit continued program execution. If the potentially excepting instruction produced the specified exception when executed, then the conditional substitution instruction substitutes the default value for the excepting instruction's result stored at the result register.
The fix-up instructions can be executed in a pipelined manner with potentially excepting and other instructions. Whether an exception was produced by a potentially excepting instruction is indicated by status bits stored in a exception register as a result of executing the instruction. Potentially excepting instructions store the status bits in the exception register during their write stage. The conditional substitution instruction acts based upon the status bits stored in the exception register during its write stage to store the specified default value in the result register if the status bits indicate one or more of the specified exceptions occurred. This permits the conditional substitution instruction which corrects the exception to follow immediately behind the excepting instruction in a pipelined computer without creating a read after write hazard.
In an alternative embodiment of the invention, a conditional substitution instruction loads a storage table with a default value which is to be substituted for the result of an instruction that produces one or more specified exceptions. This conditional substitution instruction is placed before any potentially excepting instructions it is meant to correct. Results of instructions performed by a functional unit are routed through the storage table before being stored in memory or registers. If the instruction produces one or more of the specified exceptions, the stored default value is substituted for the instruction result in its path to memory or register storage. If no specified exception was produced as a result of the instruction's execution, the instruction result continues on its path to memory or register storage.
The conditional substitution instruction according to this alternative embodiment has the advantage that it can be performed only once for any number of subsequent instructions which require the substitution of the same default value for the same specified exceptions. For example, this conditional substitution instruction can be performed once to set up the substitution of a default value for a potentially excepting instruction which is executed repetitively in a "loop" routine.
Additional features and advantages of the invention will be made apparent from the following detailed description of a preferred embodiment which proceeds with reference to the accompanying drawings.